In electronic design automation, placement assignment, i.e., the assignment of exact locations for various circuit components within a chip's core area, is important. Placement assignment affects the chip's performance and may also result in a design with excessive wirelength, which is beyond available routing resources. Accordingly, placement assignment seeks to optimize a number of objectives to ensure that a circuit meets its performance demands. One of the typical placement objectives includes minimizing the total wirelength, or the sum of the length of all the wires in the design. This not only helps minimize chip size and cost, but also minimizes power and delay, which are proportional to the wirelength and wirelength squared, respectively.
Placement assignment is particularly important in application-specific integrated circuits, or ASICs, and in gate array structures such as field-programmable gate arrays (FPGAs).
Analytical placement techniques are used to minimize wirelength. Analytical placement techniques typically optimize a quadratic wirelength objective or an approximation of the linear wirelength objective. A major concern with analytical placement techniques is that the solution of the non-linear program results in a placement with a lot of overlap among the objects. As a result, the objects have to be spread around the placement area to resolve the overlaps amongst themselves and result in a legal, non-overlapping placement. Hence, analytical placement techniques follow an iterative procedure in which they alternate between a non-linear program solve step and a spreading step, to simultaneously minimize the wirelength and spread the objects around the placement area. Before our invention, the iterative procedure of solving the non-linear program followed by the spreading step often resulted in a placement with a high wirelength.